#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long LL;
const int N = 2e6 + 10;
class Solution {
public:
    static vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> q;
        for(int i = 0; i < k; i ++)
        {
            while(q.size() && nums[q.back()] <= nums[i]) q.pop_back();
            q.push_back(i);
        }
        vector<int> ans = {nums[q.front()]};
        for(int i = k; i <= n - 1; i ++)
        {
            while(q.size() && nums[q.back()] <= nums[i]) q.pop_back();
            q.push_back(i);
            while(q.front() <= i - k) q.pop_front();
            ans.push_back(nums[q.front()]);
        }
        return ans;
    }
    static vector<int> minSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> q;
        for(int i = 0; i < k; i ++)
        {
            while(q.size() && nums[q.back()] >= nums[i]) q.pop_back();
            q.push_back(i);
        }
        vector<int> ans = {nums[q.front()]};
        for(int i = k; i <= n - 1; i ++)
        {
            while(q.size() && nums[q.back()] >= nums[i]) q.pop_back();
            q.push_back(i);
            while(q.front() <= i - k) q.pop_front();
            ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};
void solve() {
    vector<int> st1;
    int n,k;
    cin >> n >> k;
    for(int i = 1; i <= n; i ++)
    {
        int x;
        cin >> x;
        st1.push_back(x);
    }
    vector<int> ans1 = Solution::maxSlidingWindow(st1,k);
    vector<int> ans2 = Solution::minSlidingWindow(st1,k);
    for(int i = 0; i < ans1.size(); i ++)
    {
        cout << ans2[i] << ' ';
    }
    cout << endl;
    for(int i = 0; i < ans2.size(); i ++)
    {
        cout << ans1[i] << ' ';
    }
    cout << endl;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--)
    {
        solve();
    }
}